#ifndef _LISTGRAPH_H_
#define _LISTGRAPH_H_

#include "Arc.h"
#include "Graph.h"
#include "Vertex.h"

template<typename T>
class ListGraph:public Graph{

protected:
	Vertex<T>* verties;

public:
	ListGraph(int vertex_num, T* vertex_infos):Graph(vertex_num){
		this->verties = new Vertex<T>[vertex_num];
		for(int i=0;i<this->vertex_num;i++){
			this->verties[i].vertex_data = vertex_infos[i];
			this->verties[i].first_arc = 0;
		}
	}

	ListGraph(const ListGraph& g):Graph(g){
		if(this!=&g){
			this->verties = new Vertex<T>[g.vertex_num];
			for(int i=0;i<this->vertex_num;i++){
				this->verties[i] = g.verties[i];
			}
		}
	}

	ListGraph& operator=(const ListGraph& g){
		if(this!=&g){
			Graph::operator=(g);
			this->verties = new Vertex<T>[g.vertex_num];
			for(int i=0;i<this->vertex_num;i++){
				this->verties[i] = g.verties[i];
			}
		}
		return *this;
	}

	virtual ~ListGraph(){
		for(int from = 0;from<this->vertex_num;from++){
			Arc* arc = this->verties[from].first_arc;
			while(arc!=0){
				Arc* temp = arc;
				arc = arc->next_arc;
				delete temp;
			}
		}
		delete[] this->verties;
	}

	Edge GetFirstEdge(int vertex){
		Edge e(vertex,-1,0);
		if(this->verties[vertex].first_arc!=0){
			e.to = this->verties[vertex].first_arc->vertex_id;
			e.weight = this->verties[vertex].first_arc->weight;
		}
		return e;
	}

	Edge GetNextEdge(Edge pre_edge){
		int vertex = pre_edge.from;
		Edge e(vertex,-1,0);
		if(this->verties[vertex].first_arc!=0){
			Arc* arc = this->verties[vertex].first_arc;
			while(arc!=0){
				if(arc->vertex_id==pre_edge.to){
					if(arc->next_arc!=0){
						e.to = arc->next_arc->vertex_id;
						e.weight = arc->next_arc->weight;
					}
					break;
				}
				arc = arc->next_arc;
			}
		}
		return e;
	}

	bool SetEdge(int from, int to, int weight){
		if((from<this->vertex_num)&&(to<this->vertex_num)&&(from>=0)&&(to>=0)&&(from!=to)){
			Arc* newarc = new Arc(to, weight, 0);
			Arc* parc = this->verties[from].first_arc;
			if(parc == 0){// It has no arc, so the new arc is the fist arc.
				this->verties[from].first_arc = newarc;
				this->IncEdge(from, to);
				return true;
			}else{// It has arcs, so the new arc should be inserted at the correct posistion.
				Arc* pre = parc;
				if(parc->vertex_id>to){// The new arc's id is smaller than the first arc's id, so it should be inserted at the fist position
					newarc->next_arc = parc;
					this->verties[from].first_arc = newarc;
					this->IncEdge(from,to);
					return true;
				}else if(parc->vertex_id == to){ // The new arc's id equals to the first arc's id, so only set its weight.
					parc->weight = weight;
					parc = 0;
				}else{ //else to find the correct position by using a pre pointer and parcpointer.
					pre = parc;
					parc = parc->next_arc;
					while(parc!=0){
						if(parc->vertex_id<to){ // parc's id is smaller one , continue to find.
							pre = parc;
							parc = parc->next_arc;
						}
					}
					if(parc!=0){
						if(parc->vertex_id == to){//if equal to ,just set weight
							parc->weight = weight;
							return true;
						}else{ // if parc bigger than id, than insert new arc between pre and parc.
							newarc->next_arc = parc;
							pre->next_arc = newarc;
							this->IncEdge(from, to);
							return true;
						}
					}else{
						pre->next_arc = newarc;
						this->IncEdge(from, to);
						return true;
					}
				}
			}
		}
		return false;
	}

	bool DelEdge(int from, int to){
		if((from<this->vertex_num)&&(to<this->vertex_num)&&(from>=0)&&(to>=0)&&(from!=to)){
			Arc* pre = this->verties[from].first_arc;
			if(pre!=0){
				if(pre->vertex_id <to){
					Arc* parc = pre->next_arc;
					while(parc!=0){
						if(parc->vertex_id == to){
							pre->next_arc = parc->next_arc;
							delete parc;
							this->DecEdge(from,to);
							return true;
						}else if(parc->vertex_id < to){
							pre = parc;
							parc = parc->next_arc;
						}else{
							return false;
						}
					}
				}else if(pre->vertex_id == to){
					Arc* next = pre->next_arc;
					this->verties[from].first_arc = next;
					delete pre;
					this->DecEdge(from, to);
					return true;
				}else{
					return false;
				}
			}
		}

		return false;
	}

	bool IsEdge(Edge edge){
		int from = edge.from;
		int to = edge.to;
		if((from<this->vertex_num)&&(to<this->vertex_num)&&(from>=0)&&(to>=0)&&(from!=to)){
			Arc* parc = this->verties[edge.from].first_arc;
			while(parc!=0){
				if(parc->vertex_id == to){
					return true;
				}else if(parc->vertex_id < to){
					parc = parc->next_arc;
				}else{
					return false;
				}
			}
		}
		return false;
	}

	void Visit(int vertex){
		std::cout<<"["<<this->verties[vertex].vertex_data<<"]";
	}

	void DumpVertexInfo(std::ostream& os, int index){
		os<<this->verties[index].vertex_data;
	}

	void DumpGraph(std::ostream& os){
		for(int from = 0;from<this->vertex_num;from++){
			os<<this->verties[from].vertex_data;
			Arc* arc = this->verties[from].first_arc;
			while(arc!=0){
				os<<"->["<<arc->vertex_id<<"|"<<arc->weight<<"]";
				arc = arc->next_arc;
			}
			os<<"\n";
		}
		os<<"\n";
	}
};

#endif // _LISTGRAPH_H_
